package violentRecursion;

import org.junit.Test;

//博弈论问题
public class LeetCode_486 {

    @Test
    public void test_1() {
        int[] nums = {1,5,10,2};
        System.out.println("first_1: "+first_1(nums,0,nums.length-1));
        System.out.println("slow_1: "+slow_1(nums,0,nums.length-1));
    }

    @Test
    public void test_2() {
        int[] nums = {1,5,10,2};
        int[][] memo_first = new int[nums.length][nums.length];
        int[][] memo_slow = new int[nums.length][nums.length];
        //初始化记忆表，默认值-1
        for(int i=0;i<memo_first.length;i++){
            for(int j=0;j<memo_first[0].length;j++){
                memo_first[i][j] = -1;
                memo_slow[i][j] = -1;
            }
        }
        System.out.println("first_2: "+first_2(memo_first,memo_slow,nums,0,nums.length-1));
        System.out.println("slow_2: "+slow_2(memo_first,memo_slow,nums,0,nums.length-1));


    }

    @Test
    public void test_3() {
        int[] nums = {1,5,10,2};
        int[][] memo_first = new int[nums.length][nums.length];
        int[][] memo_slow = new int[nums.length][nums.length];
        //初始化记忆表，默认值-1
        for(int i=0;i<memo_first.length;i++){
            for(int j=0;j<memo_first[0].length;j++){
                memo_first[i][j] = -1;
                memo_slow[i][j] = -1;
            }
        }
        System.out.println("first_3: "+solution_3(memo_first,memo_slow,nums));


    }


    public boolean predictTheWinner(int[] nums) {
//        int first = first_1(nums,0,nums.length-1);
//        int slow = slow_1(nums,0,nums.length-1);
        int[][] memo_first = new int[nums.length][nums.length];
        int[][] memo_slow = new int[nums.length][nums.length];
        //初始化记忆表，默认值-1
        for(int i=0;i<memo_first.length;i++){
            for(int j=0;j<memo_first[0].length;j++){
                memo_first[i][j] = -1;
                memo_slow[i][j] = -1;
            }
        }
//        int first = first_2(memo_first,memo_slow,nums,0,nums.length-1);
//        int slow = slow_2(memo_first,memo_slow,nums,0,nums.length-1);
//        if (first >= slow){
//            return true;
//        }
//        return false;
        return solution_3(memo_first,memo_slow,nums);
    }

    /**
     * solution_1:暴力递归 先手情况，自己选最大
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return 最大情况
     */
    public Integer first_1(int[] nums, int left, int right){
        //1. 递归截止条件
        if(left == right) return nums[left];
        //2. 返回结果
        return Math.max(nums[left] + slow_1(nums,left+1,right),
                nums[right] + slow_1(nums,left,right-1));
    }

    /**
     * solution_1:暴力递归 后手情况，对方选最大
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return 最小情况
     */
    public Integer slow_1(int[] nums, int left, int right) {
        //1. 递归截止条件
        if(left == right) return 0;
        //2. 返回结果
        return Math.min( first_1(nums,left+1,right),
                first_1(nums,left,right-1));
    }

    /**
     * solution_2:记忆表搜索 先手情况，自己选最大
     * @param memo_first 记忆表
     * @param memo_slow 记忆表
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return 最大情况
     */
    public Integer first_2(int[][] memo_first,int[][] memo_slow,int[] nums, int left, int right){
        //1. 递归截止条件
        if(left == right) return nums[left];
        if (memo_first[left][right]!= -1){
            return memo_first[left][right];
        }
        //2. 返回结果
        int result = Math.max(nums[left] + slow_2(memo_first,memo_slow,nums,left+1,right),
                nums[right] + slow_2(memo_first,memo_slow,nums,left,right-1));
        memo_first[left][right] = result;
        return result;
    }

    /**
     * solution_2:记忆表搜索 后手情况，对方选最大
     * @param memo_first 记忆表
     * @param memo_slow 记忆表
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return 最小情况
     */
    public Integer slow_2(int[][] memo_first,int[][] memo_slow,int[] nums, int left, int right) {
        //1. 递归截止条件
        if(left == right) return 0;
        if (memo_slow[left][right]!= -1){
            return memo_slow[left][right];
        }
        //2. 返回结果
        int result = Math.min( first_2(memo_first,memo_slow,nums,left+1,right),
                first_2(memo_first,memo_slow,nums,left,right-1));
        memo_slow[left][right] = result;
        return result;
    }

    /**
     * solution_3:严格表结构 先手情况，自己选最大
     * @param memo_first 记忆表
     * @param memo_slow 记忆表
     * @param nums 数组
     * @return 最大情况
     */
    public Boolean solution_3(int[][] memo_first,int[][] memo_slow,int[] nums){

        //1. 初始化memo表
        for (int i = 0; i < memo_first.length; i++) {
            memo_first[i][i] = nums[i];
            memo_slow[i][i] = 0;
        }

        //2. 根据公式计算memo表
        for(int index=1;index<nums.length;index++){
            //2.1 填表
            for (int i = 0,j = index; j < nums.length; i++,j++) {
                memo_first[i][j] = Math.max(nums[i] + memo_slow[i+1][j], nums[j] + memo_slow[i][j-1]);
                memo_slow[i][j] = Math.min(memo_first[i+1][j], memo_first[i][j-1]);
            }
        }
        //3. 判断结果
        if (memo_first[0][nums.length-1] >= memo_slow[0][nums.length-1]){
            return true;
        }


        return false;
    }





}
